package com.myc.subjects.binarytreeandrecurtion;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * LeetCode题号：98
 *
 * 验证二叉搜索树
 *
 * 给定一个二叉树，判断其是否是一个有效的二叉搜索树。
 * 假设一个二叉搜索树具有如下特征：
 * 节点的左子树只包含小于当前节点的数。
 * 节点的右子树只包含大于当前节点的数。
 * 所有左子树和右子树自身必须也是二叉搜索树。
 *
 * 示例 1:
 * 输入:
 *     2
 *    / \
 *   1   3
 * 输出: true
 *
 * 示例 2:
 * 输入:
 *     5
 *    / \
 *   1   4
 *      / \
 *     3   6
 * 输出: false
 * 解释: 输入为: [5,1,4,null,null,3,6]。
 * 根节点的值为 5 ，但是其右子节点值为 4 。
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/validate-binary-search-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

public class Yanzhengerchasousuoshu {
    public static void main(String[] args) {
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode1 = new TreeNode(1);
        TreeNode treeNode4 = new TreeNode(4);
        TreeNode treeNode3 = new TreeNode(3);
        TreeNode treeNode6 = new TreeNode(6);

        treeNode5.left = treeNode1;
        treeNode5.right = treeNode4;
        treeNode4.left = treeNode3;
        treeNode4.right = treeNode6;

        Yanzhengerchasousuoshu y = new Yanzhengerchasousuoshu();
        System.out.println(y.isValidBST2(treeNode5));
    }

    /**
     * 方法一：先序遍历
     * 时间复杂度：O(n)
     * 自顶向下先序遍历每一个节点，通过每一个节点的上下界，来判断以该节点是否符合要求
     * 敌对同时，确定左右子节点的上下界
     */
    public boolean isValidBST1(TreeNode root) {
        return validate1(root, null, null);
    }

    //验证节点是否满足二叉搜索树要求的方法
    public boolean validate1(TreeNode root, Integer lowerBound, Integer upperBound){
        if(root == null) return true;//空树也满足二叉搜索树的特点

        //当节点值不满足上下界要求是返回false
        if(lowerBound != null && lowerBound >= root.val) return false;
        if(upperBound != null && upperBound <= root.val) return false;

        //确定左右子节点的上下界，递归遍历左右子节点。
        return validate1(root.left, lowerBound, root.val) && validate1(root.right, root.val, upperBound);
    }

    /**
     * 方法二：中序遍历
     * 时间复杂度：O(n)
     * 定义一个list来存储遍历到的节点，中序遍历到每个节点的值如果是按照从小到大排列的，则该树就是二叉搜索树
     */
    //存储节点值的List
    List<Integer> list = new ArrayList();

    public boolean isValidBST2(TreeNode root) {

        //先将树中的值中序遍历放入list
        validate2(root);

        //再看list值是不是从小到大排列的
        for(int i = 1; i < list.size(); i++){
            if(list.get(i - 1) >= list.get(i)) return false;
        }

        return true;
    }

    public void validate2(TreeNode root){
        if (root == null) return;

        validate2(root.left);
        list.add(root.val);
        validate2(root.right);
    }


    //官方题解
    //方法一：递归
    public boolean isValidBSTOfficial1(TreeNode root) {
        return isValidBSTOfficial1(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }

    public boolean isValidBSTOfficial1(TreeNode node, long lower, long upper) {
        if (node == null) {
            return true;
        }
        if (node.val <= lower || node.val >= upper) {
            return false;
        }
        return isValidBSTOfficial1(node.left, lower, node.val) && isValidBSTOfficial1(node.right, node.val, upper);
    }

    //方法二：使用栈中序遍历
    public boolean isValidBSTOfficial2(TreeNode root) {
        Deque<TreeNode> stack = new LinkedList<TreeNode>();
        double inorder = -Double.MAX_VALUE;

        while (!stack.isEmpty() || root != null) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            // 如果中序遍历得到的节点的值小于等于前一个 inorder，说明不是二叉搜索树
            if (root.val <= inorder) {
                return false;
            }
            inorder = root.val;
            root = root.right;
        }
        return true;
    }

}

/**
 * 总结：
 * 1.二叉搜索树一类问题适合使用中序遍历来解决
 * 2.中序遍历也可以利用栈来实现
 */
